#include "main.h"

struct col{
    u8 x;
    u8 y;
};      //坐标结构体

u8 position_col[X_MAX][Y_MAX]={0};//绘制迷宫数组
// 位表示含义
// 位0-3：四周墙壁信息如下
//      8
//      |
// 4 ———————— 1
//      |
//      2
// 位4：探测过程是否重复
// 位5：绘制地形是否重复

u8 text_col[Y_MAX][X_MAX]={     //测试迷宫数组
    {2,2,3,5,4,3,7,4},
    {9,15,12,2,3,12,10,2},
    {1,15,7,13,15,5,15,15},
    {3,12,10,1,14,2,10,10},
    {10,2,10,1,12,10,10,10},
    {10,9,13,7,5,13,13,14},
    {11,7,7,13,4,1,5,14},
    {8,8,9,5,5,5,5,12},
};
u8 go_strack[X_MAX*Y_MAX]={0};  //行走路径
u8 go_num=0;


int step;                               //最终需要的步数
struct col step_col[MAXSTEPS];          //最终冲刺数组
struct col ke_xi[MAXSTEPS][MAXSAME];    //柯西地图等势表
//例：ke_xi[2][3] 步数是2的第三个点的坐标
u8 jnum[MAXSTEPS]={0};                  //等势表各高度地形数目表



//检测目前位置信息
//1.采集当前格子信息
void scan_state()
{
    if(!(position_col[now_state.y][now_state.x]&16))  //未探索
    {    
        position_col[now_state.y][now_state.x]=text_col[now_state.y][now_state.x];  //记录该格信息至总表
        
    }
    now_state.door= position_col[now_state.y][now_state.x];                         //记录该格信息至目前
}

//2.选择行动策略
void move_state()
{
    if(now_state.x+now_state.y>7)  //在对角线右下方
    //>右>左>下
    {
        if((now_state.door&8) && (now_state.y!=0) && !(position_col[now_state.y-1][now_state.x]&16) ){
        //上方可走且没走过   
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过 
            now_state.y--;
            go_strack[go_num++]=8;
        }
        else if((now_state.door&1) && (now_state.x!=7) && !(position_col[now_state.y][now_state.x+1]&16) ){
        //右方可走且没走过
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过
            now_state.x++;
            go_strack[go_num++]=1;
        }
        else if((now_state.door&4) && (now_state.x!=0) && !(position_col[now_state.y][now_state.x-1]&16) ){
        //左方可走且没走过
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过
            now_state.x--;
            go_strack[go_num++]=2;
        }
        else if((now_state.door&2) && (now_state.y!=7) && !(position_col[now_state.y+1][now_state.x]&16) ){
        //下方可走且没走过
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过
            now_state.y++;
            go_strack[go_num++]=4;
        }
        else //四周都是墙壁或者全部都走过了则退后一格
        {
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过 
            go_num--;
            switch (go_strack[go_num])
            {
                case 1:
                now_state.x--;
                break;

                case 2:
                now_state.y--;
                break;

                case 4:
                now_state.x++;
                break;

                case 8:
                now_state.y++;
                break;

                default:
                printf("死路错误！");
                break;

            }
        }
    }
    else if(now_state.x+now_state.y<=7)  //在对角线左上方
    //右>上>下>左
    {
        if((now_state.door&1) && (now_state.x!=7) && !(position_col[now_state.y][now_state.x+1]&16) ){
        //右方可走且没走过
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过
            now_state.x++;
            go_strack[go_num++]=1;
        }
        else if((now_state.door&8) && (now_state.y!=0) && !(position_col[now_state.y-1][now_state.x]&16) ){
        //上方可走且没走过 
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过   
            now_state.y--;
            go_strack[go_num++]=8;
        }   
        else if((now_state.door&2) && (now_state.y!=7) && (!position_col[now_state.y+1][now_state.x]&16) ){
        //下方可走且没走过
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过
            now_state.y++;
            go_strack[go_num++]=4;
        }      
        else if((now_state.door&4) && (now_state.x!=0) && (!position_col[now_state.y][now_state.x-1]&16) ){
        //左方可走且没走过
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过
            now_state.x--;
            go_strack[go_num++]=2;
        }
        else //前方死路
        {
            position_col[now_state.y][now_state.x] |=16 ;//标记该格子已经走过 
            go_num--;
            switch (go_strack[go_num])
            {
                case 1:
                now_state.x--;
                break;

                case 2:
                now_state.y--;
                break;

                case 4:
                now_state.x++;
                break;

                case 8:
                now_state.y++;
                break;

                default:
                printf("死路错误！");
                break;

            }
        }
    }
    
    
}
//3.根据刚才所走信息绘制柯西等高图并计算最佳路径
void make_map(void)
{
    int i,j;
    int flat=0;
        ke_xi[0][0].x=0;
        ke_xi[0][0].y=7;
        jnum[0]=1;
        position_col[7][0]|=32;
        
        for(i=1;i<MAXSTEPS;i++){        
            for(j=0;j<jnum[i-1];j++){  //现在普查ke_xi[i-1][j]的关系网络
                    if((position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&1) && !(position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x+1]&32)){//右方有路且未标记
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x+1;
                        //操作下一步的柯西表
                        jnum[i]++;
                        position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x+1]|=32;   //标记已经计入登高图
                    }
                    if((position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&2) && !(position_col[ke_xi[i-1][j].y+1][ke_xi[i-1][j].x]&32)){//下方有路且未标记 
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y+1;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x;
                        jnum[i]++;
                        position_col[ke_xi[i-1][j].y+1][ke_xi[i-1][j].x]|=32;   //标记已经计入登高图
                    }
                    if((position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&4) && !(position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x-1]&32)){//左方有路且未标记
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x-1;   
                        jnum[i]++;
                        position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x-1]|=32;   //标记已经计入登高图
                    }
                    if((position_col[ke_xi[i-1][j].y][ke_xi[i-1][j].x]&8) && !(position_col[ke_xi[i-1][j].y-1][ke_xi[i-1][j].x]&32)){//上方有路且未标记
                        ke_xi[i][jnum[i]].y=ke_xi[i-1][j].y-1;
                        ke_xi[i][jnum[i]].x=ke_xi[i-1][j].x;
                        jnum[i]++;
                        position_col[ke_xi[i-1][j].y-1][ke_xi[i-1][j].x]|=32;   //标记已经计入登高图
                        
                    }
                }
        }
    i=0;
    while(jnum[i++]!=0);
    step=i-2;
    printf("\n起点至终点最少步数=%d \n",step);
    printf("2.建立等高柯西表如下\n");
    for(i=0;i<MAXSTEPS;i++) {
        printf("step=%d ",i);
        for(j=0;j<jnum[i];j++){
            printf("(%d,%d)",ke_xi[i][j].y,ke_xi[i][j].x);
        }
            
        printf("\n");
    }
    printf("回至起点最佳路径如下\n");
    step_col[step].y=0;
    step_col[step].x=7;
    printf("(0,7)");
    for(i=step-1;i>=0;i--){
        for(j=0;j<jnum[i];j++){
            flat=0;
            if((abs(ke_xi[i][j].x - step_col[i+1].x)==1&&(ke_xi[i][j].y - step_col[i+1].y==0)) ||
            abs(ke_xi[i][j].y - step_col[i+1].y)==1&&(ke_xi[i][j].x - step_col[i+1].x==0)) {//位置相邻
            
                if(ke_xi[i][j].x - step_col[i+1].x==1 && (position_col[step_col[i+1].y][step_col[i+1].x]&1)){//在右侧且没墙
                    flat=1;
                }
                else if(ke_xi[i][j].y - step_col[i+1].y==1 && (position_col[step_col[i+1].y][step_col[i+1].x]&2)){//在下侧且没墙
                    flat=1;
                }
                else if(ke_xi[i][j].x - step_col[i+1].x==-1 && (position_col[step_col[i+1].y][step_col[i+1].x]&4)){//在左侧且没墙
                    flat=1;
                }
                else if(ke_xi[i][j].y - step_col[i+1].y==-1 && (position_col[step_col[i+1].y][step_col[i+1].x]&8)){//在上侧且没墙
                    flat=1;
                }                
                if(flat){
                    step_col[i].x=ke_xi[i][j].x;
                    step_col[i].y=ke_xi[i][j].y;
                    printf("(%d,%d)",step_col[i].y,step_col[i].x);
                    break;
                }
               
            }

        }
    }


}

u8 win_or_no(void)
{
    if(now_state.x==7 && now_state.y==0){
        printf("win! the track is %d\n",go_num);
        return 1;
    }
    
    return 0;
}
int main()
{
    u8 flat=0;
    int i;
    now_state.x=0;
    now_state.y=7;
    int stop_num=0;
    printf("\n1.探索阶段收集信息展示\n");
    while(1)
    {
        scan_state();
        printf("(%c,%c)",now_state.y+'0',now_state.x+'0');              //坐标信息
        printf("(%x)",(position_col[now_state.y][now_state.x]&15));    //墙壁信息
        printf("-%c，",go_strack[go_num-1]+'0');                            //移动信息   
        if(win_or_no()) break;     
        move_state();
        if(stop_num++ ==30) {
            printf("falt!\n");
            return 0;
        }
    }
    make_map();
    printf("\n最终正向走路线：\n");
    for(i=0;i<=step;i++) printf("(%d,%d)",step_col[i].y,step_col[i].x);
    return 0;
}
